package com.base.graph;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @ClassName: AllPathsSourceTargetBfs
 * @Description: 797. 所有可能的路径
 * 用BFS找所有路径(队列)
 * @author: li
 * @Date: 2021/8/25 7:52 下午
 */
public class AllPathsSourceTargetBfs {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        int n = graph.length;
        List<List<Integer>> ret = new ArrayList<>();
        // 关键是要明白队列里面保存的是什么？队列应该要保存的是从起点到当前结点的路径
        Queue<Node<Integer>> queue = new LinkedList<>();
        queue.add(new Node<Integer>(0));
        while (!queue.isEmpty()){
            Node<Integer> cur = queue.poll();
            if (cur.node == n-1){
                ret.add(cur.path);
                continue;
            }
            for (Integer x:
                 graph[cur.node]) {
                queue.add(new Node<>(x,cur.path));

            }
        }
        return ret;

    }

    class Node<T> {
        T node;
        List<T> path;

        public Node(T node) {
            this.node = node;
            path = new LinkedList<>();
            path.add(node);
        }

        public Node(T node, List<T> path) {
            this.node = node;
            this.path = new LinkedList<>(path);
            this.path.add(node);
        }
    }
}
